package 力扣日常刷题.木22一月.第05天0112;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/12
 * @description
 */
public class Demo09回溯含相同元素集合的组合 {


    ArrayList<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,candidates.length,0,target,new ArrayList<Integer>());
        return  ans;
    }

    void dfs(int[] candidates, int n,int index,int target,ArrayList<Integer> list){
        if(target == 0){
            ans.add(new ArrayList<>(list));
            return ;
        }
        for (int i = index; i < n; i++) {
            if(candidates[i] > target){
                break;
            }
            if(i > index && candidates[i] == candidates[i-1]){
                continue;
            }
            list.add(candidates[i]);
            dfs(candidates,n,i+1,target - candidates[i],list);
            list.remove(list.size()-1);
        }
    }

}
